import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class demo {

    //    微信红包
//春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。
//请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。给定一个红包的金额数组 gifts 及它的大小 n ，
//请返回所求红包的金额。若没有金额超过总数的一半，返回0。
//    方法一
    public int getValue(int[] gifts, int n) {
        Arrays.sort(gifts);
        int count = 0;
        int mid = (n-1)/2;
        for (int i=0; i<n; i++) {
            if(gifts[i] == gifts[mid]) {
                count++;
            }
        }
        if(count > n/2) {
            return gifts[mid];
        }else {
            return 0;
        }
    }

    public int getValue2(int[] gifts, int n) {
        Arrays.sort(gifts);
        int count = 0;
        int mid = gifts[n/2];
        for (int x:gifts) {
            if (x == mid) {
                count++;
            }
        }
        if(count > n/2) {
            return mid;
        }else {
            return 0;
        }
    }


    //    方法二 hash
    public int getValue3(int[] gifts, int n) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int x : gifts) {
            if (map.containsKey(x)) {
                map.put(x,map.get(x)+1);
            }else {
                map.put(x,1);
            }

            if(map.get(x) > n/2) {
                return x;
            }
        }
        return 0;
    }















    //    计算字符串的编辑距离△△△△
//Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，
// 插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。
//例如：
//字符串A: abcdefg
//字符串B: abcdef
//通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
//要求：
//给定任意两个字符串，写出一个算法计算它们的编辑距离。
    public static int getDistance(String str1, String str2) {
        char[] ch1 = str1.toCharArray();
        char[] ch2 = str2.toCharArray();
        int len1 = ch1.length;
        int len2 = ch2.length;
        int[][] arr = new int[len1+1][len2+1];
        // 对第一列进行赋值 f(i,0) 设表示删除操作 字符串str2为空字符串 通过str1字符串经过几次删除操作可以得到
        for (int i=1; i<=len1; i++) {
            arr[i][0] = arr[i-1][0] + 1;
        }
        // 对第一行进行赋值 f(0,j) 设表示插入操作 字符串str1为空字符串 通过str2字符串经过几次插入操作可以得到
        for (int j = 1; j<=len2; j++) {
            arr[0][j] = arr[0][j-1] + 1;
        }
        // 对其他位置进行赋值
        for (int i=1; i<=len1; i++) {
            for (int j=1; j<=len2; j++) {
                // 判断该位置是删除还是插入用的步数少
                arr[i][j] = Math.min(arr[i][j-1], arr[i-1][j]) + 1;

                // 再判断和替换操作相比 哪个操作更少 如果字符相同就不需要操作不同需要继续替换操作
                if(ch1[i-1] == ch2[j-1]) {
                    // 第i个字符和第j字符相同 看看第i-1转换到j-1需要几步 + 0
                    arr[i][j] = Math.min(arr[i][j], arr[i-1][j-1]);
                }else {
                    // 第i个字符和第j字符不相同 看看第i-1转换到j-1需要几步 + 1
                    arr[i][j] = Math.min(arr[i][j], arr[i-1][j-1]+1);
                }
            }
        }
        return arr[len1][len2];
    }

    // 动态规划  将大问题转换成小问题
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String a = in.next();
        String b = in.next();
        int count = getDistance(a,b);
        System.out.println(count);
    }
}
